{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Previous Permutation With One Swap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: prevPermOpt1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #交换一次的先前排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组 <code>arr</code>（可能存在重复的元素），请你返回可在&nbsp;<strong>一次交换</strong>（交换两数字 <code>arr[i]</code> 和 <code>arr[j]</code> 的位置）后得到的、按字典序排列小于 <code>arr</code> 的最大排列。</p>\n",
    "\n",
    "<p>如果无法这么操作，就请返回原数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [3,2,1]\n",
    "<strong>输出：</strong>[3,1,2]\n",
    "<strong>解释：</strong>交换 2 和 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,1,5]\n",
    "<strong>输出：</strong>[1,1,5]\n",
    "<strong>解释：</strong>已经是最小排列\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,9,4,6,7]\n",
    "<strong>输出：</strong>[1,7,4,6,9]\n",
    "<strong>解释：</strong>交换 9 和 7\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [previous-permutation-with-one-swap](https://leetcode.cn/problems/previous-permutation-with-one-swap/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [previous-permutation-with-one-swap](https://leetcode.cn/problems/previous-permutation-with-one-swap/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,1]', '[1,1,5]', '[1,9,4,6,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        lenth=len(arr)\n",
    "        for i in range(lenth-1,0,-1):\n",
    "            if arr[i-1]>arr[i]:\n",
    "                for j in range(lenth-1,i-1,-1):\n",
    "                    if arr[j]<arr[i-1] and arr[j]!=arr[j-1]:\n",
    "                        arr[i-1],arr[j]=arr[j],arr[i-1]\n",
    "                        return arr\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        lenth=len(arr)\n",
    "        for i in range(lenth-1,0,-1):\n",
    "            if arr[i-1]>arr[i]:\n",
    "                for j in range(lenth-1,i-1,-1):\n",
    "                    if arr[j]<arr[i-1] and arr[j]!=arr[j-1]:\n",
    "                        arr[i-1],arr[j]=arr[j],arr[i-1]\n",
    "                        return arr\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                j = n - 1\n",
    "                while arr[j] >= arr[i] or arr[j] == arr[j - 1]:\n",
    "                    j -= 1\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "                break\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        idx1 = -1\n",
    "        for i in range(len(arr) - 1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                idx1 = i\n",
    "\n",
    "        if idx1 == -1:\n",
    "            return arr\n",
    "\n",
    "        idx2 = idx1 + 1\n",
    "        for i in range(idx1 + 1, len(arr)):\n",
    "            if arr[idx2] < arr[i] < arr[idx1]:\n",
    "                idx2 = i\n",
    "\n",
    "        arr[idx1], arr[idx2] = arr[idx2], arr[idx1]\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if arr[i] > arr[i+1]:\n",
    "                j = n-1\n",
    "                while arr[i] <= arr[j] or arr[j] == arr[j-1]:\n",
    "                    j -= 1\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "                break\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n=len(arr)\n",
    "        p=0\n",
    "        for i in range(n-1,0,-1):\n",
    "            if arr[i]<arr[i-1]:\n",
    "                p=i-1\n",
    "                break\n",
    "        if p==0 and arr[0]<=arr[1]:\n",
    "            return arr\n",
    "        else:\n",
    "            if arr[p]>arr[-1]:\n",
    "                arr[p],arr[-1]=arr[-1],arr[p]\n",
    "                return arr\n",
    "            else:\n",
    "                for i in range(n-1,p,-1):\n",
    "                    if arr[i]<arr[p]:\n",
    "                        while arr[i]==arr[i-1]:\n",
    "                            i-=1\n",
    "                        x=i\n",
    "                        break\n",
    "                arr[x],arr[p]=arr[p],arr[x]\n",
    "                return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "            单调栈 \n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        i =n -2 \n",
    "        while i>=0:\n",
    "            if arr[i]>arr[i+1]:\n",
    "                j = n-1\n",
    "                while arr[j]>=arr[i] or arr[j] == arr[j-1]:\n",
    "                    j-=1\n",
    "                arr[i],arr[j] =arr[j],arr[i]\n",
    "                break\n",
    "            i-=1\n",
    "        return arr \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                j = n - 1\n",
    "                while arr[i] <= arr[j] or arr[j - 1] == arr[j]:\n",
    "                    j -= 1\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "                break\n",
    "        return arr "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = arr\n",
    "        max_num = 0\n",
    "        a = -1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if arr[i] > arr[i+1]:\n",
    "                a = i\n",
    "                break\n",
    "        if a >= 0:\n",
    "            for i in range(a+1,n):\n",
    "                if arr[a]>arr[i] > max_num:\n",
    "                    index = i\n",
    "                    max_num = arr[i]\n",
    "            ans[a], ans[index] = ans[index], ans[a]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        \n",
    "        i = n - 2\n",
    "        while i >= 0 and arr[i] <= arr[i + 1]:\n",
    "            i -= 1\n",
    "        \n",
    "        if i == -1:\n",
    "            return arr\n",
    "        \n",
    "        j = n - 1\n",
    "        while arr[j] >= arr[i]:\n",
    "            j -= 1\n",
    "        \n",
    "        while j - 1 > i and arr[j] == arr[j - 1]:\n",
    "            j -= 1\n",
    "        \n",
    "        arr[i], arr[j] = arr[j], arr[i]\n",
    "\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = arr\n",
    "        max_num = 0\n",
    "        a = -1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if arr[i] > arr[i+1]:\n",
    "                a = i\n",
    "                break\n",
    "        if a >= 0:\n",
    "            for i in range(a+1,n):\n",
    "                if arr[a]>arr[i] > max_num:\n",
    "                    index = i\n",
    "                    max_num = arr[i]\n",
    "            ans[a], ans[index] = ans[index], ans[a]\n",
    "            return ans  #  [1, 9, 6, 4, 7, 7]\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            if arr[i] > arr[i+1]:\n",
    "                right = len(arr) - 1\n",
    "\n",
    "                while arr[right] == arr[right-1] or arr[right] >= arr[i]:\n",
    "                    right -= 1\n",
    "\n",
    "                arr[i],arr[right] = arr[right],arr[i]\n",
    "\n",
    "                break\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        for i in range(len(arr) - 2, -1, -1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                for j in range(i + 2, len(arr)):\n",
    "                    if arr[i] <= arr[j]:\n",
    "                        while i < j + 1:\n",
    "                            if arr[j - 1] == arr[j - 2]:\n",
    "                                j -= 1\n",
    "                            else:\n",
    "                                arr[i], arr[j - 1] = arr[j - 1], arr[i]\n",
    "                                return arr\n",
    "                arr[i], arr[len(arr) - 1] = arr[len(arr) - 1], arr[i]\n",
    "                return arr\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                j = n - 1\n",
    "                while arr[j] >= arr[i] or arr[j] == arr[j - 1]:\n",
    "                    j -= 1\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "                break\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        left=len(arr)-2\n",
    "        right=len(arr)-1\n",
    "        minindex=1\n",
    "        \n",
    "        \n",
    "        \n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "          \n",
    "            if arr[i]>arr[i+1]:\n",
    "             \n",
    "                minindex=i\n",
    "\n",
    "                cgindex=len(arr)-1\n",
    "                while arr[cgindex]>=arr[minindex]:\n",
    "\n",
    "\n",
    "\n",
    "                    cgindex-=1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                while cgindex-1>=minindex+1 and  arr[cgindex]==arr[cgindex-1]:\n",
    "                    cgindex-=1\n",
    "           \n",
    "                arr[cgindex],arr[minindex]=arr[minindex],arr[cgindex]\n",
    "                break \n",
    "        if minindex==1:return arr\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        #i尽可能靠右，若i有多个候选j，j尽可能大，若多个j相同且都最大，j尽可能靠左\n",
    "        n = len(arr)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            cur_min_idx = -1\n",
    "            for j in range(n-1,i,-1):\n",
    "                if arr[i]>arr[j]:\n",
    "                    if cur_min_idx==-1 or arr[j]>=arr[cur_min_idx]:\n",
    "                        cur_min_idx=j\n",
    "            if cur_min_idx!=-1:\n",
    "                arr[i],arr[cur_min_idx] = arr[cur_min_idx],arr[i]    \n",
    "                return arr\n",
    "        return arr\n",
    "'''\n",
    "要想交换后小于原arr，且无限接近原arr，必须使交换位置尽量靠右，以此确定从右往左的查找方向\n",
    "找i，从右向左，找第一个arr[i] > arr[i+1]的下标i，因为只有这样把arr[i]换到更后面，才能使字典序变小\n",
    "确定i后，可以发现，i下标右侧是一个升序数组，其中(可能)有比arr[i]大的，也有比arr[i]小的\n",
    "找j，从右往左，找第一个arr[j] < arr[i]的，如果有连续多个arr[j]，找最左端那个，符合无限接近的要求\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if arr[i] > arr[i+1]:\n",
    "                t = arr[i]\n",
    "                for j in range(n-1,i,-1):\n",
    "                    if arr[j] < t:\n",
    "                        for l in range(j-1,i,-1):\n",
    "                            if arr[l] < arr[j]:\n",
    "                                arr[i],arr[l+1] = arr[l+1],arr[i]\n",
    "                                return arr  \n",
    "                        arr[i],arr[i+1] = arr[i+1],arr[i]\n",
    "                        return arr    \n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            if arr[i - 1] > arr[i]:\n",
    "                for j in range(n - 1, i - 1, -1):\n",
    "                    if arr[j] < arr[i - 1] and arr[j] != arr[j - 1]:\n",
    "                        arr[i - 1], arr[j] = arr[j], arr[i - 1]\n",
    "                        return arr\n",
    "        return arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\r\n",
    "        n = len(arr)\r\n",
    "        # 从后往前找到第一个不是递增的数\r\n",
    "        for i in range(n - 2, -1, -1):\r\n",
    "            if arr[i] > arr[i + 1]:\r\n",
    "                break\r\n",
    "        else:\r\n",
    "            return arr\r\n",
    "        # 从后往前找到第一个比arr[i]小的数，交换\r\n",
    "        for j in range(n - 1, i, -1):\r\n",
    "            if arr[j] < arr[i] and arr[j] != arr[j - 1]:\r\n",
    "                arr[i], arr[j] = arr[j], arr[i]\r\n",
    "                break\r\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                j = n-1\n",
    "                while arr[j]>=arr[i] or arr[j]==arr[j-1]:\n",
    "                    j -= 1\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "                break\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        i = n-1\n",
    "        while i > 0 and arr[i-1] <= arr[i]:\n",
    "            i -= 1\n",
    "        if i == 0:\n",
    "            return arr\n",
    "        x = max(arr[k] for k in range(i,n) if arr[k] < arr[i-1])\n",
    "        for j in range(i,n):\n",
    "            if arr[j] == x:\n",
    "                break\n",
    "        arr[i-1], arr[j] = arr[j], arr[i-1]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            if arr[i] > arr[i+1]:\n",
    "                right = len(arr) - 1\n",
    "                while arr[right] == arr[right-1] or arr[i] <= arr[right]:\n",
    "                    right -= 1\n",
    "\n",
    "                    \n",
    "                arr[i],arr[right] = arr[right],arr[i]\n",
    "                break\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        idx = None\n",
    "        n = len(arr)\n",
    "        for i in range(n-1,0,-1):\n",
    "            if(arr[i-1] > arr[i]):\n",
    "                idx = i - 1\n",
    "                break\n",
    "        if(idx == None):\n",
    "            return arr \n",
    "        for i in range(n-1,idx,-1):\n",
    "            if(arr[idx] > arr[i] and arr[i] != arr[i-1]):\n",
    "                break\n",
    "        arr[idx], arr[i] = arr[i], arr[idx]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if arr[i-1] > arr[i]:\n",
    "                for j in range(n-1, i-1, -1):\n",
    "                    if arr[j] < arr[i-1] and arr[j] != arr[j-1]:\n",
    "                        arr[i-1], arr[j] = arr[j], arr[i-1]\n",
    "                        return arr\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            if arr[i] > arr[i+1]:\n",
    "                right = len(arr) - 1\n",
    "\n",
    "                while arr[right] == arr[right-1] or arr[right] >= arr[i]:\n",
    "                    right -=1\n",
    "                arr[i], arr[right] = arr[right], arr[i]\n",
    "                break\n",
    "        return arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        tmp = SortedList()\n",
    "        n = len(arr)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if len(tmp) and tmp[0][0] < arr[i]:\n",
    "                pos = tmp.bisect_left((arr[i], -1)) - 1\n",
    "                v = tmp[pos][0]\n",
    "                pos = tmp.bisect_left((v, -1))\n",
    "                p = tmp[pos][1]\n",
    "                arr[i], arr[p] = arr[p], arr[i]\n",
    "                break\n",
    "            tmp.add((arr[i], i))\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        #i尽可能靠右，若i有多个候选j，j尽可能靠左\n",
    "        n = len(arr)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            cur_min_idx = -1\n",
    "            for j in range(n-1,i,-1):\n",
    "                if arr[i]>arr[j]:\n",
    "                    if cur_min_idx==-1 or arr[j]>=arr[cur_min_idx]:\n",
    "                        cur_min_idx=j\n",
    "            if cur_min_idx!=-1:\n",
    "                arr[i],arr[cur_min_idx] = arr[cur_min_idx],arr[i]    \n",
    "                return arr\n",
    "        return arr\n",
    "'''\n",
    "要想交换后小于原arr，且无限接近原arr，必须使交换位置尽量靠右，以此确定从右往左的查找方向\n",
    "找i，从右向左，找第一个arr[i] > arr[i+1]的下标i，因为只有这样把arr[i]换到更后面，才能使字典序变小\n",
    "确定i后，可以发现，i下标右侧是一个升序数组，其中(可能)有比arr[i]大的，也有比arr[i]小的\n",
    "找j，从右往左，找第一个arr[j] < arr[i]的，如果有连续多个arr[j]，找最左端那个，符合无限接近的要求\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            if arr[i-1] > arr[i]:\n",
    "                for j in range(n - 1, -1, -1):\n",
    "                    if arr[j] < arr[i - 1] and arr[j] != arr[j - 1]: # arr[j] != arr[j - 1], 为了字典序更小，对于重复的数字要找到在最左边的\n",
    "                        arr[i - 1], arr[j] = arr[j], arr[i - 1]\n",
    "                        return arr\n",
    "        return arr "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if i == 0:\n",
    "                return arr\n",
    "            if arr[i] < arr[i-1]:\n",
    "                break\n",
    "        \n",
    "        i -= 1\n",
    "        left = i+1\n",
    "        for j in range(i+1, n):\n",
    "            if arr[j] >= arr[i]:    break\n",
    "            if arr[j] > arr[left]:\n",
    "                left = j\n",
    "        arr[left], arr[i] = arr[i], arr[left]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        #从后向前遍历, 找i arr[i] > arr[i+1]\n",
    "        #然后再从后遍历找到　arr[j] < arr[i] 交换arr[j], arr[i]\n",
    "        n = len(arr)\n",
    "        i = n - 2\n",
    "        while i >= 0 and arr[i] <= arr[i+1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return arr\n",
    "        \n",
    "        j = n - 1\n",
    "        while j > i and arr[j] >= arr[i]:\n",
    "            j -= 1\n",
    "        #去重\n",
    "        while j-1 > i and arr[j-1] == arr[j]:\n",
    "            j -= 1\n",
    "        arr[i], arr[j] = arr[j], arr[i]\n",
    "        #print(arr)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        if n == 1:\n",
    "            return arr\n",
    "\n",
    "        left_pos = n+1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                left_pos = i\n",
    "                break\n",
    "        if left_pos == n+1:\n",
    "            return arr\n",
    "\n",
    "        right_pos = left_pos + 1\n",
    "        for i in range(right_pos, n):\n",
    "            if arr[i]>=arr[left_pos]:\n",
    "                break\n",
    "            if arr[i]>arr[right_pos] and arr[i]<arr[left_pos]:\n",
    "                right_pos = i\n",
    "        arr[left_pos],arr[right_pos] = arr[right_pos],arr[left_pos]\n",
    "        return arr\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if i == 0:\n",
    "                return arr\n",
    "            if arr[i] < arr[i-1]:\n",
    "                break\n",
    "        \n",
    "        i -= 1\n",
    "        left = i+1\n",
    "        for j in range(i+1, n):\n",
    "            if arr[j] >= arr[i]:    break\n",
    "            if arr[j] > arr[left]:\n",
    "                left = j\n",
    "        arr[left], arr[i] = arr[i], arr[left]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\r\n",
    "        # 交换的具体策略是，后面的小数字要尽量大，跟前面的大数字相交换\r\n",
    "        n = len(arr)\r\n",
    "        for i in range(n - 1, 0, -1):\r\n",
    "            if arr[i - 1] > arr[i]:\r\n",
    "                for j in range(n - 1, i - 1, -1):\r\n",
    "                    if arr[j] < arr[i - 1] and arr[j] != arr[j - 1]:\r\n",
    "                        arr[i - 1], arr[j] = arr[j], arr[i - 1]\r\n",
    "                        return arr\r\n",
    "        return arr\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        i = n - 2\n",
    "        while i >= 0 and arr[i] <= arr[i + 1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return arr\n",
    "        \n",
    "        j = i + 1\n",
    "        p = j\n",
    "        while j < n:\n",
    "            if arr[j] < arr[i] and arr[j] > arr[p]:\n",
    "                p = j\n",
    "            j += 1 \n",
    "        arr[i], arr[p] = arr[p], arr[i]\n",
    "\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n=len(arr)\n",
    "        if n<2:\n",
    "            return arr\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                for j in range(n-1,i,-1):\n",
    "                    if arr[j]<arr[i]:\n",
    "                        k=j\n",
    "                        while k>-1 and  arr[k]==arr[j]:\n",
    "                            k-=1\n",
    "                        arr[i],arr[k+1]=arr[k+1],arr[i]\n",
    "                        return arr\n",
    "        return arr\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                j = n - 1\n",
    "                while arr[i] <= arr[j] or arr[j - 1] == arr[j]:\n",
    "                    j -= 1\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "                break\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        # 对于从右往左遍历的第一个升序数字，找到在右边小于这个数的最大最右数并交换\n",
    "        # 如果全程降序，返回原数组\n",
    "        n = len(arr)\n",
    "        for i, (x, y) in enumerate(pairwise(arr[::-1]), 2):\n",
    "            if x < y:\n",
    "                # 此时arr[-i]就是那个数的下标\n",
    "                break\n",
    "        else:\n",
    "            return arr\n",
    "        target = arr[-i]\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            if arr[j] < target and arr[j] != arr[j - 1]:\n",
    "                arr[-i], arr[j] = arr[j], arr[-i]\n",
    "                break\n",
    "        return arr\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prevPermOpt1(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if i == 0:\n",
    "                return arr\n",
    "            if arr[i] < arr[i-1]:\n",
    "                break\n",
    "        \n",
    "        i -= 1\n",
    "        left = i+1\n",
    "        for j in range(i+1, n):\n",
    "            if arr[j] >= arr[i]:    break\n",
    "            if arr[j] > arr[left]:\n",
    "                left = j\n",
    "        arr[left], arr[i] = arr[i], arr[left]\n",
    "        return arr"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
